\documentclass{acm_proc_article-sp}
%\documentclass[twocolumn]{article}

\usepackage[utf8]{inputenc}
\usepackage[latin]{babel}
\usepackage{graphicx}
\begin{document}

\title{Análise e Avaliação de Desempenho\\
para Esquemas de Numeração e\\
Consultas por Similaridade em Documentos XML}
\numberofauthors{2}
\author{
\alignauthor
Luiz F. Scheidegger\\
\affaddr{Instituto de Informática - UFRGS}\\
\email{lfscheidegger@inf.ufrgs.br}
\alignauthor
Felipe Cecagno\\
\affaddr{Instituto de Informática - UFRGS}\\
\email{fcecagno@inf.ufrgs.br}
}
\maketitle
\begin{abstract}
Este trabalho apresenta uma análise de desempenho para esquemas de
numeração de árvores XML mantidas em bancos de dados relacionais,
assim como resultados de experimentos feitos com consultas por
similaridade em documentos textuais. Foram utilizados três esquemas de
numeração distintos, que serão apresentados em mais detalhes no
artigo: as numerações \emph{global}, \emph{local} e
\emph{complexa}. Diversas consultas SQL foram realizadas sobre cada
esquema de numeração, e os resultados de tempo estão relatados neste
documento. Para os experimentos com similaridade, será reportada a
curvas de Precisão $\times$ Revocação média calculada a partir de 11
consultas distintas. Estas atividades foram desenvolvidas como
trabalho final da disciplina \emph{INF01006 - Projeto de Banco de
  Dados}, ministrada pelo Prof. Dr. Carlos Heuser no Instituto de
Informática da Universidade Federal do Rio Grande do Sul, durante o
período letivo de 2010/1.
\end{abstract}

\section{Introdução}
Documentos XML são uma forma muito atraente de se representar e
catalogar dados de diversos formatos, por sua simplicidade e
portabilidade, entre outros fatores. Além disso, a especificação XML,
mantida pela W3C\\ (http://www.w3.org/), é completamente aberta, de forma
que qualquer pessoa pode implementar leitores e geradores de XML.

Para documentos muito grandes, a opção de combinar a simplicidade e
generalidade de documentos XML com sistemas de banco de dados
relacionais torna-se muito atraente. Os sistemas SGBD são projetados
para lidar eficientemente com grandes volumes de dados, e a linguagem
SQL serve como uma ferramenta muito poderosa para navegar dentro do
documento XML guardado. Entretanto, a natureza inerentemente recursiva
de documentos XML faz com que o mapeamento entre um documento XML e um
conjunto de tabelas SQL não seja inteiramente óbvio. Esta necessidade
de definir um mapeamento simples e eficiente entre SQL e XML motiva o
surgimento de \emph{esquemas de numeração}. Estes esquemas são, em sua
essência, especificações para tabelas SQL que deverão guardar
documentos XML e definem, entre outras coisas, como será mantida a
ordem das linhas nas tabelas. Esquemas diferentes associam numerações
de forma diferente para cada nó da árvore XML. Por exemplo, no esquema
\emph{global}, cada nó da árvore XML recebe um identificador único e a
ordem dos nós ao se percorrer a árvore de cima para baixo, da esquerda
para a direita, é respeitada pela numeração. Já na ordem \emph{local},
cada nó recebe um identificador que só é único entre seus irmãos
(outros nós filhos do mesmo nó pai), e a ordem destes identificadores
respeita a ordem local entre estes nós. Como veremos mais adiante,
diferentes esquemas de numeração oferecem balanços entre melhor
performance em consultas, mas com maior custo de complexidade de
implementação.

Além disso, outra área de pesquisa ativa quando se trata de documentos
textuais é a área de recuperação de informações utilizando-se
\emph{consultas por similaridade}. Nesta área, o objetivo é recuperar
elementos textuais de um documento mesmo quando a busca por estes
elementos não é exata. Por exemplo, (como será visto mais adiante),
pode-se querer recuperar o item ``Horatio'' a partir de pesquisas como
``Oracio'' ou ``Horacio''. Para avaliar o desempenho de diferentes
métodos de pesquisa por similaridade pode-se utilizar a ferramente de
curvas de precisão $\times$ revocação, que medem, em linhas gerais, a
quantidade de dados recuperadas pelo sistema e a quantidade de falsos
positivos reportados.

Neste trabalho, iremos avaliar a performance de três esquemas de
numeração XML diferentes para diversas consultas XPath. Estas
consultas foram traduzidas para \emph{scripts} SQL manualmente e foram
utilizadas para medir o tempo de execução em cada um dos esquemas
observados. Fizemos testes com três métodos de numeração diferentes: o
\emph{global}, o \emph{local} e o \emph{complexo}. Na
Seção~\ref{sec:esquemas} iremos descrever cada um destes esquemas em
detalhes, e na Seção~\ref{sec:results} falaremos sobre o desempenho de
cada um deles.

Além disso, também fizemos experimentos para medir uma técnica simples
de consulta por similaridade. Para avaliar esta técnica, executamos 11
consultas por similaridade de diferentes e calculamos as curvas de
precisão $\times$ revocação de cada uma delas. Após isso, calculamos a
média entre estas curvas e reportamos esta média na
Seção~\ref{sec:results}.

%% A motivação para o surgimento de esquemas de numeração para traduzir
%% XML em um banco de dados relacional é a oportunidade de aproveitar as
%% operações otimizadas do SGBD, inexistentes no tratamento de documentos
%% XML. Em vista disso, o objetivo desse trabalho é avaliar três esquemas
%% de numeração, dois retirados de~\cite{artigo5} e o esquema proposto
%% em~\cite{artigo3}.

%% Em um segundo momento, será feita uma análise das operações de
%% consulta por similaridade de \emph{strings} propostas
%% por~\cite{similaridade}.
\pagebreak
\section{Ferramental}\label{sec:ferramental}

Todas as operações foram realizadas sobre a base de dados
\emph{hamlet.xml}~\cite{shakespeare}. A operação de carga do banco de
dados no SGBD foi realizada também utilizando a base de dados
\emph{dblp.xml}~\cite{dblp}. O banco de dados relacional utilizado foi
o \emph{MySQL} (http://www.mysql.com). O aplicativo para realizar a
carga da base de dados, bem como realizar as consultas, foi escrito na
linguagem C++, utilizando o framework \emph{Qt}
(http://qt.nokia.com). Do \emph{Qt} foram utilizados o parser XML do
tipo SAX e o driver de conexão com o banco de dados.

A máquina onde todas as medições de tempo foram executadas é um PC Intel Core 2 Quad Q6600 2.4GHz, RAM 4GB DDR2 800MHz.

\section{Esquemas de numeração}\label{sec:esquemas}

Abaixo, detalharemos brevemente o funcionamento dos esquemas de
numeração que utilizamos.

\subsection{Global}

Na ordem de numeração global~\cite{artigo5}, para cada nó do documento XML será
atribuído um número que representa a sua posição absoluta no
documento. Dessa forma, a numeração é totalmente planificada, pois não
leva em consideração a natureza hierárquica do documento XML, e
representa um percorrimento pré-numerado em profundidade, da esquerda
para a direita, no documento XML.

O ponto fraco desse esquema é que, ao realizar inserções e
atualizações, pode ser necessário renumerar parte dos nodos da árvore
para garantir a consistência do esquema, o que potencialmente
representa uma grande perda de performance. A
Figura~1 ilustra como é feita a numeração dos
nodos segundo a ordem global.

\begin{figure}[htp]\label{figure:global-tree}
\centering
\includegraphics[width=0.6\linewidth]{figures/global-tree.png}
\caption{\textbf{\emph{Esquema de numeração global~\cite{artigo5}.}}
  Na numeração global, cada nó da árvore recebe um identificador único
em todo o documento, que representa sua posição global no XML. Este
esquema de numeração é extremamente simples de implementar, mas não
apresenta performance muito boa para inserções de novas sub-árvores
dinamicamente. }
\end{figure}

\subsection{Local}

No esquema de numeração local~\cite{artigo5}, cada nó possui um número que representa
a sua posição em relação aos seus ``irmãos'', ou seja, aos outros
filhos do mesmo nó pai. Entretanto, não há garantia que a numeração
atribuída a cada nó seja única ao longo do documento inteiro, e sim
somente entre seus irmãos. Isso resolve o problema da ordem de
numeração global, em que pode ser necessário atualizar a posição de
grande parte da árvore.

Entretanto, na ordem local é difícil recuperar a informação de
ordenamento global - para recuperar a subárvore a partir de um nó, por
exemplo, é necessário utilizar uma consulta recursiva. Na ordem
global, pode-se guardar para cada nó o último nó da subárvore, e para
selecionar toda a subárvore, seleciona-se todos os identificadores de
ordem entre o nó e o último nó da subárvore. Isto evidentemente não
pode ser feito no esquema de numeração local, pois o último nodo da
sub-árvore não possui um identificador único em todo documento. Na
Figura~2 pode-se ver um exemplo de numeração
local.

\begin{figure}[htp]\label{figure:local-tree}
\centering
\includegraphics[width=0.6\linewidth]{figures/local-tree.png}
\caption{\textbf{\emph{Esquema de numeração local~\cite{artigo5}.}}
  Na numeração local, cada nodo possui um identificador que só é único
entre seus irmãos no mesmo nível da árvore. Além disto, este
identificador codifica a ordem deste elemento entre seus irmãos. A
vantagem deste esquema de numeração é que não é necessário alterar o
documento inteiro durante inserções e remoções de
sub-árvores. Entretanto, torna-se mais difícil recuperar informações
sobre a ordem global dos elementos. }
\end{figure}

\subsection{Complexo}

O esquema de numeração utilizado em~\cite{artigo3}, denominado de
\emph{complexo}, é um esquema esparso e propõe que cada nó da árvore
seja armazenado com um identificador de posição global, e um
identificador que indica o tamanho da subárvore. Através desses
identificadores, espera-se reduzir eventuais renumerações da árvore,
uma vez que são deixados ``espaços'' para inserções futuras, e uma
remoção não implica em renumeração. A Figura~3
ilustra o funcionamento do sistema de numeração complexo.

\begin{figure}[htp]\label{figure:complex-tree}
\centering
\includegraphics[width=0.6\linewidth]{figures/complex-tree.png}
\caption{\emph{\textbf{Esquema de numeração complexo~\cite{artigo3}.}}
Na numeração complexa, cada nodo possuí duas informações: um
identificador de ordem global e um ponteiro para o último elemento de
sua sub-árvore. Além disso, deixa-se intervalos de números vagos entre
os números utilizados pelo esquema, que permitem maior facilidade para
inserção de novas sub-árvores no esquema. }
\end{figure}

\section{Experimentos}\label{sec:results}
Nesta seção, iremos discutir em detalhes os resultados obtidos de
nosso procedimento experimental para avaliar a performance de bancos
de dados SQL para armazenar documentos grandes XML. Falaremos sobre
resultados de consultas XPath traduzidas para consultas SQL, assim
como alterações realizadas sobre o banco (como inserções e
remoções de linhas) e finalmente sobre as curvas de precisão $\times$
revocação que foram obtidas em nossos experimentos com consultas por
similaridade.

\subsection{Consultas XPath e Alterações no banco}
Avaliamos a performance de três esquemas de numeração diferentes
(Global, Local e Complexa) para XML executando um conjunto de
consultas XPath sobre o documento \emph{hamlet.xml} e medindo o tempo
de execução. Além disso, executamos duas alterações sobre o banco de
dados: fizemos a duplicação do último ato do documento (colocando-o a
frente do primeiro ato), e a exclusão do primeiro ato. O tempo foi
tomado como uma média entre 10 repetições da mesma consulta ou alteração - foram 11 no total, mas retirando-se a primeira. Para todas as consultas,
utilizamos uma tabela auxiliar de caminhos no SGBD. A
Tabela~1 lista todas as consultas XPath que foram
realizadas, com uma legenda que deve ser utilizada para consultar a
Tabela~2.

\begin{table}\label{table:legend}
\begin{tabular}{|c|l|}
\hline
\multicolumn{2}{|c|}{\textbf{Consultas}} \\
\hline
\hline
{\tiny \textbf{C1}} & {\tiny /PLAY}  \\
{\tiny \textbf{C2}} & {\tiny /PLAY/ACT//SPEECH}  \\
{\tiny \textbf{C3}} & {\tiny /PLAY/ACT/SCENE/SPEECH} \\
{\tiny \textbf{C4}} & {\tiny /PLAY/ACT/SCENE/SPEECH[SPEAKER='BERNARDO']} \\
{\tiny \textbf{C5}} & {\tiny /PLAY/ACT[TITLE='ACTI']/SCENE/SPEECH[SPEAKER='BERNARDO']} \\
{\tiny \textbf{C6}} & {\tiny /PLAY/ACT/SCENE/SPEECH[2]} \\
\hline
\end{tabular}
\begin{tabular}{|c|l|}
\hline
\multicolumn{2}{|c|}{\textbf{Alterações}} \\
\hline
\hline
\textbf{A1} & Carga do \emph{dblp.xml} \\
\textbf{A2} & Carga do \emph{hamlet.xml} \\
\textbf{A3} & Cópia do Último Ato \\
\textbf{A4} & Remoçao do Primeiro Ato \\
\hline
\end{tabular}
\caption{\emph{\textbf{Operações Executadas.}} Nestas tabelas constam as
  operações de alteração e consulta executadas sobre o documento \emph{hamlet.xml} armazenado em um SGBD utilizando-se diferentes esquemas de numeração. Além disso, a alteração A1 é a carga do documento \emph{dblp.xml} no banco de dados, utilizando os mesmos esquemas de numeração. Esta legenda deve ser utilizada para referência na Tabela~2.}
\end{table}

\begin{table}\label{table:results}
\centering
\begin{tabular}{r|r|r|r|}
\cline{2-4} 
& \multicolumn{3}{|c|}{\textbf{Tempo de Execução}} \\
\cline{2-4}
& \multicolumn{1}{|c|}{\textbf{Global}} & 
  \multicolumn{1}{|c|}{\textbf{Local}} & 
  \multicolumn{1}{|c|}{\textbf{Complexa}} \\
\hline
\multicolumn{1}{|c|}{\textbf{A1}} & 9min48s (77\%) & 10min3s (79\%)   & \textbf{12min40s} \\
\multicolumn{1}{|c|}{\textbf{A2}} & 180ms (97\%) & \textbf{185ms} & 175ms (94\%) \\
\multicolumn{1}{|c|}{\textbf{A3}} & 164ms (72\%) & \textbf{229ms} & 150ms (66\%) \\
\multicolumn{1}{|c|}{\textbf{A4}} & 62ms (26\%) & \textbf{239ms} & 20ms (8\%) \\
\multicolumn{1}{|c|}{\textbf{C1}} & 135ms (56\%) & \textbf{239ms} & 138ms (56\%) \\
\multicolumn{1}{|c|}{\textbf{C2}} & 240ms (93\%) & \textbf{258ms} & 239ms (93\%) \\
\multicolumn{1}{|c|}{\textbf{C3}} & \textbf{243ms} & 241ms (99\%) & 238ms (98\%) \\
\multicolumn{1}{|c|}{\textbf{C4}} & 134ms (99\%) & \textbf{135ms} & 129ms (96\%) \\
\multicolumn{1}{|c|}{\textbf{C5}} & 148ms (96\%) & \textbf{154ms} & \textbf{154ms} \\
\multicolumn{1}{|c|}{\textbf{C6}} & 136ms (87\%) & \textbf{157ms} & 134ms (85\%) \\
\hline
\end{tabular}
\caption{\emph{\textbf{Resultados Obtidos.}} Tempo de execução para
  cada operação constante na Tabela~1. Cada valor numérico está acompanhado da porcentagem
  relativa ao valor máximo em sua linha, para fins de comparação, e o
  valor máximo está destacado em negrito. }
\end{table}

Para maximizar a performance de nossos experimentos, todas as
consultas e alterações foram feitas diretamente com \emph{scripts}
SQL, i.e., não utilizamos passos intermediários desenvolvidos em outra
linguagem de programação. Isso permite minimizar o sobrecusto de troca
de contexto entre o SGBD e nossa aplicação, já que todas as consultas
e alterações são disparadas com somente uma chamada SQL. Entretanto,
isto tornou nossos scripts SQL mais complexos do que estritamente
necessário para gerar os resultados. A implementação de consultas
recursivas para resolver sub-árvores inteiras do documento XML foram
particularmente complexas em nossa implementação.

\begin{figure}\label{figure:buffer_sizes}
\centering
\includegraphics[width=0.8\linewidth]{figures/buffer_sizes.pdf}
\caption{\emph{\textbf{Tempo para carga $\times$ tamanho de buffer. }}
  Nesta figura, pode-se notar o desempenho da operação de carga do
  banco de dados relacional com documentos XML ao se variar o número
  de inserções SQL que são executadas a cada chamada para o
  SGBD. Pode-se observar que o tempo diminui drasticamente ao se
  empregar um buffer, e que um buffer de tamanho 500 é ideal. }
\end{figure}

Ao executar a carga do banco de dados, existe uma preocupação
importante com minimizar o número de acessos ao SGBD pela
aplicação cliente que está fazendo o \emph{parsing} do documento
XML. Para isso, implementamos um \emph{buffer} parcial de
consultas, que acumula um certo número de operações de inserção SQL e
as envia de uma única vez para o SGBD, ao invés de executá-las
individualmente. A Figura~4 mostra a
performance da carga do banco de dados ao variar o tamanho deste
\emph{buffer}. Escolhendo o tamanho ótimo nos gerou um ganho de
performance na ordem de 8$\times$ (fizemos isto somente para a carga,
pois as alterações e consultas são resolvidas com apenas um acesso e executadas inteiramente em SQL).

Na Tabela~2 estão os resultados de performance de
todas as operações realizadas sobre o banco de dados. Pode-se
imediatamente observar que todas as consultas demoraram na ordem de
grandeza de 0,3 segundos para ser executadas. Além disso, pode-se ver
que em todas as operações a diferença entre o esquema de melhor e pior
performance não passou de aproximadamente 60\% (que pode ser observado
na operação \textbf{C1}), à excessão de \textbf{A3}. A discrepância
evidente da operação \textbf{A3} pode ser explicada pelo fato de que
ela se trata de uma remoção na ordem complexa. Nesta ordem, não é
necessário nenhum tipo de renumeração após uma remoção, como ocorre nas ordens global e local. Além disso, como este esquema de ordenamento mantém em cada raiz de sub-árvore o índice de seu último descendente, é muito fácil remover a sub-árvore inteira com poucos comandos SQL.

De um modo geral, a ordem de numeração complexa é a que apresenta melhor desempenho nas alterações e consultas. A carga do \emph{dblp.xml} no banco de dados é o item em que a ordem de numeração complexa apresenta o pior desempenho - o método de carga requer duas passadas no documento para gerar a numeração correta, e isso representa um tempo significativo para arquivos grandes.

Mesmo com um desempenho superior na ordem de numeração complexa, os
resultados da Tabela~2 mostram que estas diferenças
são pouco expressivas. De fato, todos os esquemas de
numeração possuem um desempenho bastante semelhante. O motivo pelo
qual isso ocorre é que nós utilizamos uma tabela auxiliar com os
caminhos para os nós da árvore XML, o que torna simplificado o caminhamento na árvore, uma vez que a tabela de caminhos remove a necessidade de JOIN para acessar as subárvores. A
principal conclusão que podemos traçar destes resultados é que o
melhor investimento para maximizar a performance de consultas XPath
sobre documentos armazenados em um banco de dados relacional é o uso
da tabela auxiliar que guarda os caminhos para os nós.

\subsection{Consultas por Similaridade}

O algoritmo utilizado para estimar similaridade entre strings foi retirado de~\cite{similaridade} e é baseado na divisão das strings em partes chamadas de \emph{grams}. O número de \emph{grams} idênticos entre duas strings é o coeficiente de similaridade - quanto maior é o coeficiente, mais similar uma string é da outra.

Na implementação do algoritmo, dois parâmetros devem ser configurados manualmente. Um deles é o tamanho de cada gram, chamado de \emph{q}, e o outro é a maior diferença entre strings, chamado de \emph{k}. O \emph{q} utilizado foi 3, e o \emph{k} foi configurado para se ajustar dinamicamente ao tamanho da string procurada. O ajuste do parâmetro \emph{k} é bastante crítico pois tal valor é utilizado no algoritmo para estimar a posição do \emph{gram} procurado em relação aos \emph{grams} gerados no banco. Se o \emph{k} for muito grande, strings grandes terão muitos \emph{grams} em comum, embora esses grams não correspondam aos \emph{grams} do string procurado, pois a diferença na posição deles é limitada ao \emph{k}. Se o \emph{k} for muito pequeno, serão encontrados poucos \emph{grams} comuns, e a consulta será menos precisa.

Para avaliar nossa implementação de consultas por similaridade,
executamos uma série de consultas sobre o banco de dados construído a
partir do documento \emph{hamlet.xml}, utilizando-se o esquema de
numeração global. Fizemos um total de 11 consultas diferentes, e
coletamos as curvas de precisão $\times$ revocação para cada uma
delas. As consultas utilizadas podem ser encontradas na
Tabela~3.

\begin{table}
\label{table:similarity}
\begin{tabular}{|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Consultas por Similaridade}}\\
\hline
\hline
\small{\textbf{Consulta}} & \small{\textbf{Valor Esperado}} & \small{\textbf{\# Ocorrências}}\\
\hline
\tiny{Oracio} & \tiny{Horatio} & \tiny{112}\\
\tiny{Horacio} & \tiny{Horatio} & \tiny{112}\\
\tiny{Oreitio} & \tiny{Horatio} & \tiny{112}\\
\hline
\tiny{Marcel} & \tiny{Marcellus} & \tiny{37}\\
\tiny{Marcelo} & \tiny{Marcellus} & \tiny{37}\\
\hline
\tiny{Act} & \tiny{\{Act I $\cdots$ Act V\}} & \tiny{5}\\
\tiny{Acto} & \tiny{\{Act I $\cdots$ Act V\}} & \tiny{5}\\
\tiny{Ato} & \tiny{\{Act I $\cdots$ Act V\}} & \tiny{5}\\
\hline
\tiny{Gertrudes} & \tiny{Queen Gertrude} & \tiny{69}\\
\tiny{Gertrud} & \tiny{Queen Gertrude} & \tiny{69}\\
\tiny{Rainha Gertrudes} & \tiny{Queen Gertrude} & \tiny{69}\\
\hline
\end{tabular}
\caption{\emph{\textbf{Consultas por Similaridade.}} Nesta tabela
  estão listadas todas as consultas por similaridade que foram
  executadas sobre o documento \emph{hamlet.xml}. A coluna mais da
  esquerda indica os valores que foram usados para a consulta,
  enquanto a coluna central indica a palavra que deve ser retornada, e
  a coluna mais à direita mostra a quantidade de ocorrências desta
  palavra no documento. }
\end{table}

Como pode-se observar na Tabela~\ref{table:similarity}, cada consulta
por similaridade diferente gerou um número distinto de ocorrências do
termo procurado. Devido a isto, as curvas de precisão
$\times$ revocação individuais de cada consulta possuem um número
particular de pontos. Para gerar a curva média (que pode ser observada
na Figura~5), foi necessário reamostrar todas estas
curvas para 10 pontos distribuídos uniformemente entre 0 e 1. Uma vez
que as curvas foram reamostradas, a curva média pôde ser calculada
simplesmente fazendo-se uma média aritmética de cada ponto para
incluí-lo na curva final.

\begin{figure}
\label{figure:similarity}
\centering
\includegraphics[width=0.8\linewidth]{figures/similarity.pdf}
\caption{\emph{\textbf{Curva de Precisão vs. Revocação média.}} Esta
  curva demonstra os fatores de precisão e revocação média obtidos em
  nossos experimentos com consultas por similaridade. Esta curva média
  foi obtida por reamostragem das curvas das pesquisas individuais e
  tirando a média aritmética de cada um dos pontos de revocação. }
\end{figure}

\section{Conclusões}
Neste relatório, apresentamos uma análise de performance para
consultas e alterações de bancos de dados relacionais contendo
documentos XML mantidos com três diferentes esquemas de numeração: o
\emph{global}, o \emph{local} e o \emph{complexo}. Mostramos o tempo
para executar estas consultas, e pudemos concluir que existem poucas
diferenças significativas de performance entre os diferentes esquemas,
exceto quando se trata da remoção de uma sub-árvore no esquema
complexo. Além disso, concluímos que a principal maneira de melhorar a
performance de consultas XPath sobre documentos XML mantidos em bancos
de dados relacionais é fazendo uso de uma tabela auxiliar que contém
os caminhos para cada nodo da árvore XML.

Também fizemos testes e avaliações de desempenho para um esquema
simples de consultas por similaridade, também sobre documentos
textuais XML mantidos em bancos de dados relacionais. Para validar
este esquema, implementamos 11 consultas por similaridade diferentes,
e construímos suas curvas de precisão $\times$ revocação. Estas 11
curvas foram combinadas em uma curva média que apresentamos neste
relatório. A partir desta curva, pudemos ver que o esquema de
similaridade que implementamos (baseado em $q-grams$ e distância por
número de $q-grams$ em comum) é bastante eficiente, com uma precisão
média mínima de aproximadamente 80\%.
%\pagebreak
\bibliographystyle{plain}
\bibliography{refs}
\balancecolumns
\end{document}
